home *** CD-ROM | disk | FTP | other *** search
/ QRZ! Ham Radio 8 / QRZ Ham Radio Callsign Database - Volume 8.iso / mac / files / t_sys5 / 92052tar.gz / 920528.tar / iproute.c < prev    next >
C/C++ Source or Header  |  1992-05-28  |  18KB  |  704 lines
  1. /* @(#) $Header: iproute.c,v 1.12 92/05/28 13:50:18 deyke Exp $ */
  2.  
  3. /* Lower half of IP, consisting of gateway routines
  4.  * Includes routing and options processing code
  5.  *
  6.  * Copyright 1991 Phil Karn, KA9Q
  7.  */
  8. #include "global.h"
  9. #include "mbuf.h"
  10. #include "iface.h"
  11. #include "timer.h"
  12. #include "internet.h"
  13. #include "ip.h"
  14. #include "netuser.h"
  15. #include "icmp.h"
  16. #include "rip.h"
  17. #include "trace.h"
  18. #include "pktdrvr.h"
  19. #include "bootp.h"
  20.  
  21. struct route *Routes[32][HASHMOD];      /* Routing table */
  22. struct route R_default = {              /* Default route entry */
  23.     NULLROUTE, NULLROUTE,
  24.     0,0,0,
  25.     RIP_INFINITY            /* Init metric to infinity */
  26. };
  27.  
  28. static struct rt_cache Rt_cache;
  29.  
  30. /* Initialize modulo lookup table used by hash_ip() in pcgen.asm */
  31. void
  32. ipinit()
  33. {
  34.     int i;
  35.  
  36.     for(i=0;i<256;i++)
  37.         Hashtab[i] = i % HASHMOD;
  38. }
  39.  
  40. /* Route an IP datagram. This is the "hopper" through which all IP datagrams,
  41.  * coming or going, must pass.
  42.  *
  43.  * "rxbroadcast" is set to indicate that the packet came in on a subnet
  44.  * broadcast. The router will kick the packet upstairs regardless of the
  45.  * IP destination address.
  46.  */
  47. int
  48. ip_route(i_iface,bp,rxbroadcast)
  49. struct iface *i_iface;  /* Input interface */
  50. struct mbuf *bp;        /* Input packet */
  51. int rxbroadcast;        /* True if packet had link broadcast address */
  52. {
  53.     struct ip ip;                   /* IP header being processed */
  54.     int16 ip_len;                   /* IP header length */
  55.     int16 length;                   /* Length of data portion */
  56.     int32 gateway;                  /* Gateway IP address */
  57.     register struct route *rp;      /* Route table entry */
  58.     struct iface *iface;            /* Output interface, possibly forwarded */
  59.     int16 offset;                   /* Offset into current fragment */
  60.     int16 mf_flag;                  /* Original datagram MF flag */
  61.     int strict = 0;                 /* Strict source routing flag */
  62.     char prec;                      /* Extracted from tos field */
  63.     char del;
  64.     char tput;
  65.     char rel;
  66.     int16 opt_len;          /* Length of current option */
  67.     char *opt;              /* -> beginning of current option */
  68.     int i;
  69.     struct mbuf *tbp;
  70.     int ckgood = IP_CS_OLD; /* Has good checksum without modification */
  71.     int pointer;            /* Relative pointer index for sroute/rroute */
  72.  
  73.     if(i_iface != NULLIF){
  74.         ipInReceives++; /* Not locally generated */
  75.         i_iface->iprecvcnt++;
  76.     }
  77.     if(len_p(bp) < IPLEN){
  78.         /* The packet is shorter than a legal IP header */
  79.         ipInHdrErrors++;
  80.         free_p(bp);
  81.         return -1;
  82.     }
  83.     /* Sneak a peek at the IP header's IHL field to find its length */
  84.     ip_len = (bp->data[0] & 0xf) << 2;
  85.     if(ip_len < IPLEN){
  86.         /* The IP header length field is too small */
  87.         ipInHdrErrors++;
  88.         free_p(bp);
  89.         return -1;
  90.     }
  91.     if(cksum(NULLHEADER,bp,ip_len) != 0){
  92.         /* Bad IP header checksum; discard */
  93.         ipInHdrErrors++;
  94.         free_p(bp);
  95.         return -1;
  96.     }
  97.     /* Extract IP header */
  98.     ntohip(&ip,&bp);
  99.  
  100.     if(ip.version != IPVERSION){
  101.         /* We can't handle this version of IP */
  102.         ipInHdrErrors++;
  103.         free_p(bp);
  104.         return -1;
  105.     }
  106.  
  107.     if(i_iface != NULLIF && ismyaddr(ip.source) == NULLIF)
  108.         rt_add(ip.source, 32, 0L, i_iface, 1L, 0x7fffffff / 1000, 0);
  109.  
  110.     /* Trim data segment if necessary. */
  111.     length = ip.length - ip_len;    /* Length of data portion */
  112.     trim_mbuf(&bp,length);
  113.  
  114.     /* If we're running low on memory, return a source quench */
  115.     if(!rxbroadcast && availmem() != 0)
  116.         icmp_output(&ip,bp,ICMP_QUENCH,0,NULLICMP);
  117.  
  118.     /* Process options, if any. Also compute length of secondary IP
  119.      * header in case fragmentation is needed later
  120.      */
  121.     strict = 0;
  122.     for(i=0;i<ip.optlen;i += opt_len){
  123.  
  124.         /* First check for the two special 1-byte options */
  125.         switch(ip.options[i] & OPT_NUMBER){
  126.         case IP_EOL:
  127.             goto no_opt;    /* End of options list, we're done */
  128.         case IP_NOOP:
  129.             opt_len = 1;
  130.             continue;       /* No operation, skip to next option */
  131.         }
  132.         /* Not a 1-byte option, so ensure that there's at least
  133.          * two bytes of option left, that the option length is
  134.          * at least two, and that there's enough space left for
  135.          * the specified option length.
  136.          */
  137.         if(ip.optlen - i < 2
  138.          || ((opt_len = uchar(ip.options[i+1])) < 2)
  139.          || ip.optlen - i < opt_len){
  140.             /* Truncated option, send ICMP and drop packet */
  141.             if(!rxbroadcast){
  142.                 union icmp_args icmp_args;
  143.  
  144.                 icmp_args.pointer = IPLEN + i;
  145.                 icmp_output(&ip,bp,ICMP_PARAM_PROB,0,&icmp_args);
  146.             }
  147.             free_p(bp);
  148.             return -1;
  149.         }
  150.         opt = &ip.options[i];
  151.  
  152.         switch(opt[0] & OPT_NUMBER){
  153.         case IP_SSROUTE:        /* Strict source route & record route */
  154.             strict = 1;     /* note fall-thru */
  155.         case IP_LSROUTE:        /* Loose source route & record route */
  156.             /* Source routes are ignored unless we're in the
  157.              * destination field
  158.              */
  159.             if(opt_len < 3){
  160.                 /* Option is too short to be a legal sroute.
  161.                  * Send an ICMP message and drop it.
  162.                  */
  163.                 if(!rxbroadcast){
  164.                     union icmp_args icmp_args;
  165.  
  166.                     icmp_args.pointer = IPLEN + i;
  167.                     icmp_output(&ip,bp,ICMP_PARAM_PROB,0,&icmp_args);
  168.                 }
  169.                 free_p(bp);
  170.                 return -1;
  171.             }
  172.             if(ismyaddr(ip.dest) == NULLIF)
  173.                 break;  /* Skip to next option */
  174.             pointer = uchar(opt[2]);
  175.             if(pointer + 4 > opt_len)
  176.                 break;  /* Route exhausted; it's for us */
  177.  
  178.             /* Put address for next hop into destination field,
  179.              * put our address into the route field, and bump
  180.              * the pointer. We've already ensured enough space.
  181.              */
  182.             ip.dest = get32(&opt[pointer]);
  183.             put32(&opt[pointer],locaddr(ip.dest));
  184.             opt[2] += 4;
  185.             ckgood = IP_CS_NEW;
  186.             break;
  187.         case IP_RROUTE: /* Record route */
  188.             if(opt_len < 3){
  189.                 /* Option is too short to be a legal rroute.
  190.                  * Send an ICMP message and drop it.
  191.                  */
  192.                 if(!rxbroadcast){
  193.                     union icmp_args icmp_args;
  194.  
  195.                     icmp_args.pointer = IPLEN + i;
  196.                     icmp_output(&ip,bp,ICMP_PARAM_PROB,0,&icmp_args);
  197.                 }
  198.                 free_p(bp);
  199.                 return -1;
  200.             }
  201.             pointer = uchar(opt[2]);
  202.             if(pointer + 4 > opt_len){
  203.                 /* Route area exhausted; send an ICMP msg */
  204.                 if(!rxbroadcast){
  205.                     union icmp_args icmp_args;
  206.  
  207.                     icmp_args.pointer = IPLEN + i;
  208.                     icmp_output(&ip,bp,ICMP_PARAM_PROB,0,&icmp_args);
  209.                 }
  210.                 /* Also drop if odd-sized */
  211.                 if(pointer != opt_len){
  212.                     free_p(bp);
  213.                     return -1;
  214.                 }
  215.             } else {
  216.                 /* Add our address to the route.
  217.                  * We've already ensured there's enough space.
  218.                  */
  219.                 put32(&opt[pointer],locaddr(ip.dest));
  220.                 opt[2] += 4;
  221.                 ckgood = IP_CS_NEW;
  222.             }
  223.             break;
  224.         }
  225.     }
  226. no_opt:
  227.  
  228.     /* See if it's a broadcast or addressed to us, and kick it upstairs */
  229.     if(ismyaddr(ip.dest) != NULLIF || rxbroadcast ||
  230.         (WantBootp && bootp_validPacket(&ip, &bp))){
  231. #ifdef  GWONLY
  232.     /* We're only a gateway, we have no host level protocols */
  233.         if(!rxbroadcast)
  234.             icmp_output(&ip,bp,ICMP_DEST_UNREACH,
  235.              ICMP_PROT_UNREACH,NULLICMP);
  236.         ipInUnknownProtos++;
  237.         free_p(bp);
  238. #else
  239.         ip_recv(i_iface,&ip,bp,rxbroadcast);
  240. #endif
  241.         return 0;
  242.     }
  243.     /* Packet is not destined to us. If it originated elsewhere, count
  244.      * it as a forwarded datagram.
  245.      */
  246.     if(i_iface != NULLIF)
  247.         ipForwDatagrams++;
  248.  
  249.     /* Adjust the header checksum to allow for the modified TTL */
  250.     ip.checksum += 0x100;
  251.     if((ip.checksum & 0xff00) == 0)
  252.         ip.checksum++;  /* end-around carry */
  253.  
  254.     /* Decrement TTL and discard if zero. We don't have to check
  255.      * rxbroadcast here because it's already been checked
  256.      */
  257.     if(--ip.ttl == 0){
  258.         /* Send ICMP "Time Exceeded" message */
  259.         icmp_output(&ip,bp,ICMP_TIME_EXCEED,0,NULLICMP);
  260.         ipInHdrErrors++;
  261.         free_p(bp);
  262.         return -1;
  263.     }
  264.     /* Look up target address in routing table */
  265.     if((rp = rt_lookup(ip.dest)) == NULLROUTE){
  266.         /* No route exists, return unreachable message (we already
  267.          * know this can't be a broadcast)
  268.          */
  269.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_HOST_UNREACH,NULLICMP);
  270.         free_p(bp);
  271.         ipOutNoRoutes++;
  272.         return -1;
  273.     }
  274.     rp->uses++;
  275.  
  276.     /* Check for output forwarding and divert if necessary */
  277.     iface = rp->iface;
  278.     if(iface->forw != NULLIF)
  279.         iface = iface->forw;
  280.  
  281.     /* Find gateway; zero gateway in routing table means "send direct" */
  282.     if(rp->gateway == 0)
  283.         gateway = ip.dest;
  284.     else
  285.         gateway = rp->gateway;
  286.  
  287.     if(strict && gateway != ip.dest){
  288.         /* Strict source routing requires a direct entry
  289.          * Again, we know this isn't a broadcast
  290.          */
  291.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_ROUTE_FAIL,NULLICMP);
  292.         free_p(bp);
  293.         ipOutNoRoutes++;
  294.         return -1;
  295.     }
  296.     prec = PREC(ip.tos);
  297.     del = ip.tos & DELAY;
  298.     tput = ip.tos & THRUPUT;
  299.     rel = ip.tos & RELIABILITY;
  300.  
  301.     if(ip.length <= iface->mtu){
  302.         /* Datagram smaller than interface MTU; put header
  303.          * back on and send normally.
  304.          */
  305.         if((tbp = htonip(&ip,bp,ckgood)) == NULLBUF){
  306.             free_p(bp);
  307.             return -1;
  308.         }
  309.         iface->ipsndcnt++;
  310.         return (*iface->send)(tbp,iface,gateway,prec,del,tput,rel);
  311.     }
  312.     /* Fragmentation needed */
  313.     if(ip.flags.df){
  314.         /* Don't Fragment set; return ICMP message and drop */
  315.         union icmp_args icmp_args;
  316.  
  317.         icmp_args.mtu = iface->mtu;
  318.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_FRAG_NEEDED,&icmp_args);
  319.         free_p(bp);
  320.         ipFragFails++;
  321.         return -1;
  322.     }
  323.     /* Create fragments */
  324.     offset = ip.offset;
  325.     mf_flag = ip.flags.mf;          /* Save original MF flag */
  326.     while(length != 0){             /* As long as there's data left */
  327.         int16 fragsize;         /* Size of this fragment's data */
  328.         struct mbuf *f_data;    /* Data portion of fragment */
  329.  
  330.         /* After the first fragment, should remove those
  331.          * options that aren't supposed to be copied on fragmentation
  332.          */
  333.         ip.offset = offset;
  334.         if(length + ip_len <= iface->mtu){
  335.             /* Last fragment; send all that remains */
  336.             fragsize = length;
  337.             ip.flags.mf = mf_flag;  /* Pass original MF flag */
  338.         } else {
  339.             /* More to come, so send multiple of 8 bytes */
  340.             fragsize = (iface->mtu - ip_len) & 0xfff8;
  341.             ip.flags.mf = 1;
  342.         }
  343.         ip.length = fragsize + ip_len;
  344.  
  345.         /* Duplicate the fragment */
  346.         dup_p(&f_data,bp,offset,fragsize);
  347.         if(f_data == NULLBUF){
  348.             free_p(bp);
  349.             ipFragFails++;
  350.             return -1;
  351.         }
  352.         /* Put IP header back on, recomputing checksum */
  353.         if((tbp = htonip(&ip,f_data,IP_CS_NEW)) == NULLBUF){
  354.             free_p(f_data);
  355.             free_p(bp);
  356.             ipFragFails++;
  357.             return -1;
  358.         }
  359.         /* and ship it out */
  360.         if((*iface->send)(tbp,iface,gateway,prec,del,tput,rel) == -1){
  361.             ipFragFails++;
  362.             free_p(bp);
  363.             return -1;
  364.         }
  365.         iface->ipsndcnt++;
  366.         ipFragCreates++;
  367.         offset += fragsize;
  368.         length -= fragsize;
  369.     }
  370.     ipFragOKs++;
  371.     free_p(bp);
  372.     return 0;
  373. }
  374. int
  375. ip_encap(bp,iface,gateway,prec,del,tput,rel)
  376. struct mbuf *bp;
  377. struct iface *iface;
  378. int32 gateway;
  379. int prec;
  380. int del;
  381. int tput;
  382. int rel;
  383. {
  384.     struct ip ip;
  385.  
  386.     dump(iface,IF_TRACE_OUT,CL_NONE,bp);
  387.     iface->rawsndcnt++;
  388.     iface->lastsent = secclock();
  389.  
  390.     if(gateway == 0L){
  391.         /* Gateway must be specified */
  392.         ntohip(&ip,&bp);
  393.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_HOST_UNREACH,NULLICMP);
  394.         free_p(bp);
  395.         ipOutNoRoutes++;
  396.         return -1;
  397.     }
  398.     /* Encapsulate in an IP packet from us to the gateway */
  399.     return ip_send(INADDR_ANY,gateway,IP_PTCL,0,0,bp,0,0,0);
  400. }
  401.  
  402. /* Add an entry to the IP routing table. Returns 0 on success, -1 on failure */
  403. struct route *
  404. rt_add(target,bits,gateway,iface,metric,ttl,private)
  405. int32 target;           /* Target IP address prefix */
  406. unsigned int bits;      /* Size of target address prefix in bits (0-32) */
  407. int32 gateway;          /* Optional gateway to be reached via interface */
  408. struct iface *iface;    /* Interface to which packet is to be routed */
  409. int32 metric;           /* Metric for this route entry */
  410. int32 ttl;              /* Lifetime of this route entry in sec */
  411. char private;           /* Inhibit advertising this entry ? */
  412. {
  413.     struct route *rp,**hp;
  414.     struct route *rptmp;
  415.     int32 gwtmp;
  416.  
  417.     if(iface == NULLIF)
  418.         return NULLROUTE;
  419.  
  420.     if(bits > 32)
  421.         bits = 32;              /* Bulletproofing */
  422.  
  423.     if(bits == 32 && ismyaddr(target))
  424.         return NULLROUTE;       /* Don't accept routes to ourselves */
  425.  
  426.     /* Mask off don't-care bits of target */
  427.     target &= ~0L << (32-bits);
  428.  
  429.     /* Encapsulated routes must specify gateway, and it can't be
  430.      *  ourselves
  431.      */
  432.     if(iface == &Encap && (gateway == 0 || ismyaddr(gateway)))
  433.         return NULLROUTE;
  434.  
  435.     Rt_cache.route = NULLROUTE;     /* Flush cache */
  436.  
  437.     /* Zero bits refers to the default route */
  438.     if(bits == 0){
  439.         rp = &R_default;
  440.     } else {
  441.         rp = rt_blookup(target,bits);
  442.     }
  443.     if(rp == NULLROUTE){
  444.         /* The target is not already in the table, so create a new
  445.          * entry and put it in.
  446.          */
  447.         rp = (struct route *)callocw(1,sizeof(struct route));
  448.         /* Insert at head of table */
  449.         rp->prev = NULLROUTE;
  450.         hp = &Routes[bits-1][hash_ip(target)];
  451.         rp->next = *hp;
  452.         if(rp->next != NULLROUTE)
  453.             rp->next->prev = rp;
  454.         *hp = rp;
  455.         rp->uses = 0;
  456.     }
  457.     rp->target = target;
  458.     rp->bits = bits;
  459.     rp->gateway = gateway;
  460.     rp->metric = metric;
  461.     rp->iface = iface;
  462.     rp->flags = private ? RTPRIVATE : 0;    /* Should anyone be told of this route? */
  463.     rp->timer.func = rt_timeout;  /* Set the timer field */
  464.     rp->timer.arg = (void *)rp;
  465.     set_timer(&rp->timer,ttl*1000L);
  466.     stop_timer(&rp->timer);
  467.     start_timer(&rp->timer); /* start the timer if appropriate */
  468.  
  469.     /* Check to see if this created an encapsulation loop */
  470.     gwtmp = gateway;
  471.     for(;;){
  472.         rptmp = rt_lookup(gwtmp);
  473.         if(rptmp == NULLROUTE)
  474.             break;  /* No route to gateway, so no loop */
  475.         if(rptmp->iface != &Encap)
  476.             break;  /* Non-encap interface, so no loop */
  477.         if(rptmp == rp){
  478.             rt_drop(target,bits);   /* Definite loop */
  479.             return NULLROUTE;
  480.         }
  481.         if(rptmp->gateway != 0)
  482.             gwtmp = rptmp->gateway;
  483.     }
  484.     route_savefile();
  485.     return rp;
  486. }
  487.  
  488. /* Remove an entry from the IP routing table. Returns 0 on success, -1
  489.  * if entry was not in table.
  490.  */
  491. int
  492. rt_drop(target,bits)
  493. int32 target;
  494. unsigned int bits;
  495. {
  496.     register struct route *rp;
  497.  
  498.     Rt_cache.route = NULLROUTE;     /* Flush the cache */
  499.  
  500.     if(bits == 0){
  501.         /* Nail the default entry */
  502.         stop_timer(&R_default.timer);
  503.         R_default.iface = NULLIF;
  504.         return 0;
  505.     }
  506.     if(bits > 32)
  507.         bits = 32;
  508.  
  509.     /* Mask off target according to width */
  510.     target &= ~0L << (32-bits);
  511.  
  512.     /* Search appropriate chain for existing entry */
  513.     for(rp = Routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  514.         if(rp->target == target)
  515.             break;
  516.     }
  517.     if(rp == NULLROUTE)
  518.         return -1;      /* Not in table */
  519.  
  520.     stop_timer(&rp->timer);
  521.     if(rp->next != NULLROUTE)
  522.         rp->next->prev = rp->prev;
  523.     if(rp->prev != NULLROUTE)
  524.         rp->prev->next = rp->next;
  525.     else
  526.         Routes[bits-1][hash_ip(target)] = rp->next;
  527.  
  528.     free((char *)rp);
  529.     return 0;
  530. }
  531. #if 1
  532. char Hashtab[256];      /* Modulus lookup table */
  533.  
  534. /* Compute hash function on IP address */
  535. int16
  536. hash_ip(addr)
  537. register int32 addr;
  538. {
  539.     register int16 ret;
  540.  
  541.     ret = hiword(addr);
  542.     ret ^= loword(addr);
  543.     return (int16)(ret % HASHMOD);
  544. }
  545. #endif
  546. #ifndef GWONLY
  547. /* Given an IP address, return the MTU of the local interface used to
  548.  * reach that destination. This is used by TCP to avoid local fragmentation
  549.  */
  550. int16
  551. ip_mtu(addr)
  552. int32 addr;
  553. {
  554.     register struct route *rp;
  555.     struct iface *iface;
  556.  
  557.     rp = rt_lookup(addr);
  558.     if(rp == NULLROUTE || rp->iface == NULLIF)
  559.         return 0;
  560.  
  561.     iface = rp->iface;
  562.     if(iface->forw != NULLIF)
  563.         return iface->forw->mtu;
  564.     else
  565.         return iface->mtu;
  566. }
  567. /* Given a destination address, return the IP address of the local
  568.  * interface that will be used to reach it. If there is no route
  569.  * to the destination, pick the first non-loopback address.
  570.  */
  571. int32
  572. locaddr(addr)
  573. int32 addr;
  574. {
  575.     register struct route *rp;
  576.     struct iface *ifp;
  577.  
  578.     if(ismyaddr(addr) != NULLIF)
  579.         return addr;    /* Loopback case */
  580.  
  581.     rp = rt_lookup(addr);
  582.     if(rp != NULLROUTE && rp->iface != NULLIF)
  583.         ifp = rp->iface;
  584.     else {
  585.         /* No route currently exists, so just pick the first real
  586.          * interface and use its address
  587.          */
  588.         for(ifp = Ifaces;ifp != NULLIF;ifp = ifp->next){
  589.             if(ifp != &Loopback && ifp != &Encap)
  590.                 break;
  591.         }
  592.     }
  593.     if(ifp == NULLIF || ifp == &Loopback)
  594.         return 0;       /* No dice */
  595.  
  596.     if(ifp == &Encap){
  597.         /* Recursive call - we assume that there are no circular
  598.          * encapsulation references in the routing table!!
  599.          * (There is a check at the end of rt_add() that goes to
  600.          * great pains to ensure this.)
  601.          */
  602.         return locaddr(rp->gateway);
  603.     }
  604.     if(ifp->forw != NULLIF)
  605.         return ifp->forw->addr;
  606.     else
  607.         return ifp->addr;
  608. }
  609. #endif
  610. /* Look up target in hash table, matching the entry having the largest number
  611.  * of leading bits in common. Return default route if not found;
  612.  * if default route not set, return NULLROUTE
  613.  */
  614. struct route *
  615. rt_lookup(target)
  616. int32 target;
  617. {
  618.     register struct route *rp;
  619.     int bits;
  620.     int32 tsave;
  621.     int32 mask;
  622.  
  623.     /* Examine cache first */
  624.     if(target == Rt_cache.target && Rt_cache.route != NULLROUTE)
  625.         return Rt_cache.route;
  626.  
  627.     tsave = target;
  628.  
  629.     mask = ~0;      /* All ones */
  630.     for(bits = 31;bits >= 0; bits--){
  631.         target &= mask;
  632.         for(rp = Routes[bits][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  633.             if(rp->target == target){
  634.                 /* Stash in cache and return */
  635.                 Rt_cache.target = tsave;
  636.                 Rt_cache.route = rp;
  637.                 return rp;
  638.             }
  639.         }
  640.         mask <<= 1;
  641.     }
  642.     if(R_default.iface != NULLIF){
  643.         Rt_cache.target = tsave;
  644.         Rt_cache.route = &R_default;
  645.         return &R_default;
  646.     } else
  647.         return NULLROUTE;
  648. }
  649. /* Search routing table for entry with specific width */
  650. struct route *
  651. rt_blookup(target,bits)
  652. int32 target;
  653. unsigned int bits;
  654. {
  655.     register struct route *rp;
  656.  
  657.     if(bits == 0){
  658.         if(R_default.iface != NULLIF)
  659.             return &R_default;
  660.         else
  661.             return NULLROUTE;
  662.     }
  663.     /* Mask off target according to width */
  664.     target &= ~0L << (32-bits);
  665.  
  666.     for(rp = Routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  667.         if(rp->target == target){
  668.             return rp;
  669.         }
  670.     }
  671.     return NULLROUTE;
  672. }
  673. /* Scan the routing table. For each entry, see if there's a less-specific
  674.  * one that points to the same interface and gateway. If so, delete
  675.  * the more specific entry, since it is redundant.
  676.  */
  677. void
  678. rt_merge(trace)
  679. int trace;
  680. {
  681.     int bits,i,j;
  682.     struct route *rp,*rpnext,*rp1;
  683.  
  684.     for(bits=32;bits>0;bits--){
  685.         for(i = 0;i<HASHMOD;i++){
  686.             for(rp = Routes[bits-1][i];rp != NULLROUTE;rp = rpnext){
  687.                 rpnext = rp->next;
  688.                 for(j=bits-1;j >= 0;j--){
  689.                     if((rp1 = rt_blookup(rp->target,j)) != NULLROUTE
  690.                      && rp1->iface == rp->iface
  691.                      && rp1->gateway == rp->gateway){
  692.                         if(trace > 1)
  693.                             printf("merge %s %d\n",
  694.                              inet_ntoa(rp->target),
  695.                              rp->bits);
  696.                         rt_drop(rp->target,rp->bits);
  697.                         break;
  698.                     }
  699.                 }
  700.             }
  701.         }
  702.     }
  703. }
  704.